/*
 * @lc app=leetcode.cn id=133 lang=javascript
 *
 * [133] 克隆图
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * 1. 拷贝所有节点
 * 2. 拷贝所有的边
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
  if (!node) {
    return;
  }
  const visited = new Map();
  //   // 1. 深度优先遍历所有节点
  //   const dfs = (n) => {
  //     const nCopy = new Node(n.val);
  //     visited.set(n, nCopy);
  //     console.log(n.val);
  //     (n.neighbors || []).forEach((ne) => {
  //       if (!visited.has(ne)) {
  //         dfs(ne);
  //       }
  //       nCopy.neighbors.push(visited.get(ne));
  //     });
  //   };
  //   dfs(node);
  //   广度优先遍历
  visited.set(node, new Node(node.val));
  const q = [node];
  while (q.length) {
    const n = q.shift();
    (n.neighbors || []).forEach((ne) => {
      if (!visited.has(ne)) {
        q.push(ne);
        visited.set(ne, new Node(ne.val));
      }
      visited.get(n).neighbors.push(visited.get(ne));
    });
  }
  return visited.get(node);
};
// @lc code=end
